The present invention relates to a data processing apparatus and method for processing a variable length code with carry signals.
Generally, an arithmetic unit in an arithmetic coding unit generates a variable length code each time the arithmetic coding of one symbol is performed, and generates a carry signal such as a carry signal and a borrow signal depending on the contents of computation. At this time, because the code has a variable length, code length information for indicating the length of the generated code is outputted at the same time. The length of the variable length code is between 0 and a certain value N. The value N depends on register length in the arithmetic coding unit, called an augend register or a code interval register (hereinafter referred to as A register).
Typical arithmetic coding systems include the JBIG system standardized by the JBIG (Joint Bi-level Image Experts Group) that is an agent of the ITU (International Telecommunications Union), and the Q-coder proposed by IBM Corporation. In the following description, the arithmetic coding system will not be limited to a specific one, assuming that general arithmetic coding is used. However, technical terms may be used inevitably for convenience of explanation because terms and concepts are not popular, and in this case, the JBIG that is a standard system will be applied.
Whether or not the value of the A register is within a predetermined range is checked (it is usually considered that the value falls within a predetermined range if the value of the most significant bit of this register A is xe2x80x981xe2x80x99) each time arithmetic coding of one symbol is performed, and if the value falls within the range, nothing is done and then arithmetic coding is performed for a next symbol. In this case, the generated code length is 0 bit. In contrast, if the value does not fall within the range, shift processing is performed so that the value of the A register falls within the predetermined range, and at the same time shift processing is performed for a cord register (hereinafter referred to as C register) being a register based on which codes are generated. This is usually referred to as normalization processing (hereinafter referred to as shift processing or normalization processing).
At this time, a shifted bit number is a generated code length, and information shifted out from the C register is a code. Specific examples are shown in FIGS. 1A to 1F.
FIGS. 1A to 1F show values of the arithmetic register before and after shift processing. Assume that the lengths of the A register and C register are N+1 bits, respectively, and the values of the respective registers immediately after arithmetic coding (before shift processing) are those shown in FIG. 1A. In this case, it is determined that the value falls within a predetermined range because the most significant bit of the A register is xe2x80x981xe2x80x99, and thus shift processing is not performed (FIG 1B), and the generated code length is 0 bit.
Then, assume that the values of the respective registers immediately after arithmetic coding are those shown in FIG. 1C. In this case, it is determined that the value does not fall within a predetermined range because the most significant bit of the A register is xe2x80x980xe2x80x99, and thus shift processing is performed. For this shift processing, left shifting is carried out until the most significant bit of the A register becomes xe2x80x981xe2x80x99. In the example shown in FIG 1C, 5-bit left shifting is performed. This 5-bit shifting is also performed for the C register. Thus, a 5-bit code of xe2x80x9c10100xe2x80x9d is shifted out from the C register, and this code is outputted as a code. When such 5-bit shifting is performed, xe2x80x980xe2x80x99 is added to the lower five bits of the respective registers. As a result, the values of the respective registers after shift processing are those as shown in FIG. 1D.
Then, assume that the values of the respective registers immediately after arithmetic coding are those in FIG. 1E. In this case, the value of the A register is the minimum, and the generated code is a N-bit code (upper N bits of the C register). If the value of the A register is smaller than this value, the value equals to xe2x80x980xe2x80x99, and there is no possibility that the most significant bit is xe2x80x981xe2x80x99 with any bit shifting, leading to a breakdown of shift processing. The values of respective registers after shift processing in FIG. 1E are those as shown in FIG. 1F.
In the above description, relationship between the values of registers for use in arithmetic computation and the codes and code lengths generated for the values has been shown.
If information generated in the computation unit is only a variable length code and code length information, the process is simple. If the variable length codes are concatenated seamlessly, and are then cut by a predetermined length, a code of fixed length can be outputted.
A Huffman encoder that is one type of encoders for entropy coding outputs only a variable code and code length information, and thus a code of fixed length can be obtained only with the aforesaid processing. What performs such processing is generally called a (length fixation) packing circuit, and has been used for many years as with the Huffman code. One example of the packing circuit is shown in FIG. 2 for reference.
FIG. 2 shows the configuration of a general packing circuit for length fixation. The packing circuit shown in FIG. 2 accepts variable length codes of 0 to 15 bits, couple the codes and output them in 16 bits.
In FIG. 2, reference numeral 201 denotes a terminal for inputting variable length codes of 0 to 15 bits, reference numeral 202 denotes a terminal for inputting code length information of 4 bits, reference numeral 203 denotes an adder for adding inputted code length information to the bit number of codes remaining in the packing circuit, reference numeral 204 denotes a carry output of the adder 203, reference numeral 205 denotes lower a 4-bit output of the adder 203, reference numeral 206 denotes a D flip-flop for latching the carry output 204, reference numeral 207 denotes a 4-bit D flip-flop for latching the lower 4-bit output 205 of the adder 203, reference numeral 208 denotes an output signal of the D flip-flop 206, reference numeral 210 denotes a barrel shifter for shifting an input variable length code, reference numeral 211 denotes a coupler for concatenating the code remaining in the packing circuit to the input variable length code, reference numeral 212 denotes a 30-bit D flip-flop for latching the codes concatenated by the coupler 211, and reference numeral 213 denotes a shifter for shifting by 16 bits the concatenated code outputted from the D flip-flop 212.
Operations of the packing circuit shown in FIG. 2 will be briefly described below.
First, a hold value of the D flip-flop 207 is cleared to zero by initialization processing. Then, a first variable length code is inputted from the terminal 201, and is sent straightly to the coupler 211 without being shifted by the barrel shifter 210, and the input variable length code is at the head of the concatenated code. If the code length of this variable length code is S bits, code length information of the value S is inputted to the terminal 202 at the inputting of the variable length code. The code length information is latched in the D flip-flop 207 via the adder 203. Thereby, the first variable length code of S bits is captured in the packing circuit.
Then, assume that a variable length code of T bits is inputted. The variable length code inputted from the terminal 201 is shifted by S bits by the barrel shifter 210, and is sent to the coupler 211. The coupler 211 couples the T-bit variable length code shifted by S bits to the rear of the first inputted S-bit variable length code, and newly generates a concatenated code of (S+T) bits. The concatenated code is latched in the D flip-flop 212. On the other hand, the value T being code information is inputted in the terminal 202, and S+T is computed by the adder 203. If S+T less than 16 holds, then the concatenated code is retained, and a variable length code to be inputted next is further concatenated.
If S+Txe2x89xa716 holds, then the concatenated code has a length of 16 bits or larger, and thus leading 16 bits are outputted to the outside by a signal line 215. In this case, the carry signal 204 is generated during computation of S+T in the adder 203, xe2x80x981xe2x80x99 is captured in the D flip-flop 206, and the signal 208 also takes on xe2x80x981xe2x80x99. The signal 208 is a signal indicating that a 16-bit code is outputted to the outside, and the 16-bit code of the signal line 215 is a valid output when the signal takes on xe2x80x981xe2x80x99. The carry is generated, whereby the value of lower 4 bits of the adder 203 becomes S+Txe2x88x9216, and the result of the addition is retained in the D flip-flop 207.
Thereafter, processing same as the above processing is repeated to couple variable length codes one after another and outputs the same as 16-bit codes. If the output of the arithmetic encoder constituted only by the variable length code and information of the code length, this simple packing circuit can satisfy the needs.
Furthermore, in FIG. 2, the lengths of variable length codes that can be inputted are 0 to 15 to show the simplest packing circuit, but the lengths of variable length codes that can be inputted may be 0 to 16 by slightly modifying the adder 203.
If the length of the fixed length code to be outputted is 16, the variable length code that can be inputted may be 16 at the maximum if the worst condition (the case where the longest code is consecutively inputted) is taken into consideration. This is because assume that the maximum code length of input is 17 bits, and when the 17-bit code is consecutively inputted, the length of codes remaining in the packing circuit is increased by one bit with one time input/output, and thus the number of bits that can be retained in the internal register is exceeded.
A carry signal that is another output of the arithmetic unit will now be described.
In arithmetic coding, information of whether a symbol that is encoded is consistent with a predicted value and a probability estimation value of likelihood that the predicted value does not appear are used. The former information is used for selection of computation, and the latter probability estimation value is used for actual computation.
For the A register, generally, any one of the value obtained by subtracting the probability estimation value from the A register and the probability estimation value is selected based on the aforesaid consistency/inconsistency information, and is used as a new value of the A register. Regardless of which value is selected, the value of the A register is smaller than the previous value, and shift processing is not performed if the value falls within a predetermined range, but left shifting is performed until the value falls with in the predetermined range if it falls below the predetermined range.
For the C register, there are a variety of computation methods such as computation suitable for software processing, computation for hard ware processing, subtraction computation and addition computation, even if only the JBIG system is considered. In this case, whether the type of computation for the C register is addition or subtraction computation is a matter.
If the computation is addition computation, whether nothing is added or some value is added to the C register is selected based on the aforesaid consistency/inconsistency information. In this case, addition computation may generate a carry signal. This is because there is a possibility that the value of the C register before computation is already sufficiently large, and some value is added thereto, whereby an overflow occurs in the register. If the overflow occurs, the carry signal is outputted to the outside, and remaining values are made to be new values of the C register (values before shift processing), thereby making it possible to move to a next process without breakdown.
If the computation is subtraction computation, whether nothing is subtracted or some value is subtracted from the C register is selected based on the aforesaid consistency/inconsistency information. In this case, subtraction computation may generate a borrow signal. This is because there is a possibility that the value of the C register before computation is already sufficiently small, and some value is subtracted therefrom, whereby an overflow occurs negatively in the register. If the overflow occurs, the borrow signal is outputted to the outside, and remaining values are made to be new values of the C register (values before shift processing), thereby making it possible to move to a next process without breakdown.
A new circuit is required for processing such a carry signal.
A method in which an addition circuit for adding the carry signal to a general packing circuit as shown in FIG. 2 is added to process the carry signal has been proposed (Japanese Patent Publication No. 7-123228). In this method, however, a new carry occurs due to the added addition circuit, and after all, a carry signal appears again in the output subjected to packing processing.
Explanation will be given using FIG. 3 showing only input/output relationship of the packing circuit for making it easier to understand. FIG. 3 shows an input/output signal of the packing circuit with input/output of carry signals. The following can be easily understood, compared to FIG. 2.
The packing circuit has input/output signals same as those of a conventional packing circuit.
Input of the carry signal occurs, and associated therewith, output of the carry signal occurs.
FIG. 4 shows a packing circuit with input/output of carry signals and the input/output signal of a circuit processing the output of the packing circuit. A new circuit 401 as shown in FIG. 4 is required separately for processing a new carry signal generated in the packing circuit with input/output of carry signals, and the circuit is inserted in a next layer, and finally only a 16-bit output signal with no carry signal and a signal indicating presence/absence of output remain. This processing method leads to such the configuration because carry processing is left over.
As described above, according to the above described prior arts, when a variable length code supplied together with a carry signal is converted into a defined fixed length code with no carry signal, good compatibility with other entropy coding to generate only the variable length code (meaning no carry signal) is obtained, and thus another (length fixation) packing circuit is required for converting the variable length code generated from the entropy encoder into a fixed length code.
The present invention has been made in view of the above described problems, and its object is to provide a data converting method and apparatus enabling a variable length code with a carry signal to be converted into a variable length code with no carry signal.
According to the present invention, the foregoing object is attained by providing a data processing apparatus, comprising: concatenation means for incorporating inputted carry signals in a retained remaining code, and concatenating thereto an inputted variable length code to generate a concatenated code; outputting means for separating from the concatenated code a defined code portion that is not influenced by the carry signal and outputting the same; retaining means for retaining an undefined code portion obtained by removing the defined code portion from the concatenated code, as a remaining code for use in the concatenation means; first acquisition means for acquiring the code length of the undefined code when the whole of the concatenated code is an undefined code; and generating means for generating a predetermined defined code having a code length obtained with the first acquisition means and outputting the same.
The present invention further provides a data processing apparatus, comprising: concatenation means for incorporating inputted carry signals in a retained remaining code, and concatenating thereto an inputted variable length code to generate a concatenated code; first outputting means for separating from the concatenated code a defined code portion that is not influenced by the carry signal, and outputting the defined code portion and the code length thereof; retaining means for retaining an undefined code portion obtained by removing the defined code portion from the concatenated code, as a remaining code for use in the incorporating means; first acquisition means for acquiring the code length of the defined code if the whole of the concatenated code is an undefined code; and second outputting means for outputting the code length obtained by the first acquisition means.
The present invention further provides a data processing method, comprising: a concatenating step of incorporating inputted carry signals in a retained remaining code, and concatenating thereto an inputted variable length code to generate a concatenated code; an outputting step of separating from the concatenated code a defined code portion that is not influenced by the carry signal and outputting the same; a retaining step of retaining an undefined code portion obtained by removing the defined code portion from the concatenated code, as a remaining code for use in the concatenating step; a first acquiring step of acquiring the code length of the undefined code when the whole of the concatenated code is an undefined code; and a generating step of generating a predetermined defined code having a code length obtained by the first acquiring step and outputting the same.
The present invention further provides a data processing method, comprising: a concatenating step of incorporating inputted carry signals in a retained remaining code, and concatenating thereto an inputted variable length code to generate a concatenated code; a first outputting step of separating from the concatenated code a defined code portion that is not influenced by the carry signal, and outputting the defined code portion and the code length thereof; a retaining step of retaining an undefined code portion obtained by removing the defined code portion from the concatenated code, as a remaining code for use in the incorporating step; a first acquiring step of acquiring the code length of the defined code if the whole of the concatenated code is an undefined code; and a second outputting step of outputting the code length obtained in the first acquiring step.